package demo15_1;

public class Test15_1 {
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode list1, MySingleList.ListNode list2) {
        MySingleList.ListNode newHead = new MySingleList.ListNode();
        MySingleList.ListNode th = newHead;
        while (list1 != null && list2 != null) {
            if (list1.value < list2.value) {
                th.next =list1;
                list1 = list1.next;
            }else {
                th.next = list2;
                list2 = list2.next;
            }
            th = th.next;
        }
        if (list1 == null) {
            th.next = list2;
        }
        if (list2 == null) {
            th.next = list1;
        }
        return newHead.next;
    }

    private static int size(MySingleList.ListNode head) {
        int count = 0;
        MySingleList.ListNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public static MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        //1.分别求两个链表的长度
        int lenA = size(headA);
        int lenB = size(headB);

        MySingleList.ListNode pL = headB;
        MySingleList.ListNode pS = headA;

        //求两个长度的差值
        int len = lenA - lenB;
        if(len < 0) {
            //说明B长
            len = lenB - lenA;
        }else {
            pL = headA;
            pS = headB;
        }
        //pL指向长的，pS指向短的
        //2.让最长的链表先走差值步
        for(int i = 0;i < len; i++) {
            pL = pL.next;
        }

        while(pL != pS) {
            pL = pL.next;
            pS = pS.next;
        }

        if(pL == null) {
            return null;
        }
        return pL;
    }

    public static void createIntersect(MySingleList.ListNode headA,MySingleList.ListNode headB) {
        MySingleList.ListNode cur = headA;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = headB;
    }

    public static boolean hasCycle(MySingleList.ListNode head) {
        if(head == null) {
            return false;
        }
        MySingleList.ListNode fast = head;
        MySingleList.ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addFirst(75);
        mySingleList1.addFirst(46);
        mySingleList1.addFirst(32);
        mySingleList1.addFirst(24);
        mySingleList1.addFirst(13);
        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addFirst(75);
        mySingleList2.addFirst(50);
        mySingleList2.addFirst(33);
//        MySingleList.ListNode RET = mergeTwoLists(mySingleList1.head,mySingleList2.head);
//        mySingleList1.display(RET);
//        createIntersect(mySingleList1.head,mySingleList2.head);
//        MySingleList.ListNode mySingleList3 = getIntersectionNode(mySingleList1.head,mySingleList2.head);
//        System.out.println(mySingleList3.value);
        MySingleList.ListNode cur = mySingleList1.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = mySingleList1.head.next.next;
        Boolean ret = hasCycle(mySingleList1.head);
        System.out.println(ret);
    }
    public static void main2(String[] args) {
//        MySingleList mySingleList = new MySingleList();
//        mySingleList.addFirst(1);
//        mySingleList.addFirst(2);
//        mySingleList.addFirst(3);
//        mySingleList.addFirst(4);
//        mySingleList.addFirst(5);
//        mySingleList.addFirst(6);
////        mySingleList.clear();
//        System.out.println("============");

        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();
        mySingleList.display();
//        MySingleList.ListNode newhead = mySingleList.reverseList();
        //mySingleList.display();
//        mySingleList.display(newhead);
        MySingleList.ListNode ret = mySingleList.middleNode();
        System.out.println(ret.value);


    }
    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
//        mySingleList.createList();
//        mySingleList.display();
//        System.out.println(mySingleList.size());
//        System.out.println(mySingleList.contains(44));
//        mySingleList.addFirst(88);
//        mySingleList.display();
////        System.out.println(123);
//        mySingleList.addLast(88);
//        mySingleList.display();
//        mySingleList.addIndex(3,999);
//        mySingleList.display();
        mySingleList.addIndex(0,99);
        mySingleList.display();
        mySingleList.addIndex(0,88);
        mySingleList.display();
        mySingleList.addIndex(1,888);
        mySingleList.display();
//        mySingleList.addIndex(-5,55);
//        mySingleList.addIndex(1,55);
//        mySingleList.display();

        mySingleList.remove(99);
        mySingleList.display();
        mySingleList.remove(15);
    }

}
